1. Field of the Invention
The present invention relates to an image processing device, an image processing method and an image processing program for extracting a plurality of candidate points belonging to a predetermined structure from image data and performing matching between the candidate points and nodes of a known shape model which represents a shape of the predetermined structure.
2. Description of the Related Art
Automatic extraction of a structure, such as coronary arteries, from three-dimensional image data, such as volume data, has conventionally been conducted (see, for example, U.S. Patent Application Publication No. 20110085701, which will hereinafter be referred to as Patent Document 1). Patent Document 1 discloses extracting a plurality of candidate points forming coronary arteries based on values of voxel data forming volume data, selecting, from the extracted candidate points, a corresponding point corresponding to each model label forming a shape model such that the corresponding points form a graph structure that is most similar to the shape model, and determining paths connecting the selected corresponding points by selectively connecting the candidate points to achieve a minimal cost based on a predetermined index value.
The selection of the corresponding points is achieved by providing an evaluation function for evaluating a similarity between the graph structure formed by the set of candidate points corresponding to the model labels and the shape model, and finding an optimal solution (a mapping between the candidate points and the model labels) of the evaluation function. In this case, a set C of feasible solutions x of the evaluation function is usually defined as Equation (1) below:
                    C        =                              {                                                            x                  ∈                                                            {                                              0                        ,                        1                                            }                                                              P                      ×                      Q                                                                      |                                                                            ∑                                              Sp                        ∈                        P                                                                                                                                  ⁢                                                                                  ⁢                    xSpTq                                    ≤                  1                                            ,                                                                    ∑                                          Tq                      ∈                      Q                                                                                                                      ⁢                                                                          ⁢                  xSpTq                                ≤                1                            ,                              ∀                                  Sp                  ∈                                      P                    ⁢                                                                                  ⁢                    and                    ⁢                                                                                  ⁢                                          ∀                                              Tq                        ∈                        Q                                                                                                                  }                    .                                              (          1          )                ,            where P represents a set of candidate points Sp, Q represents a set of model labels Tq, xSpTq is a binary variable indicating a mapping relationship between an arbitrary candidate point Sp and an arbitrary model label Tq and has a value of 1 if the candidate point Sp is mapped with the model label Tq or a value of 0 if the candidate point Sp is not mapped with the model label Tq, and x is a P×Q-dimensional vector with values of the variable xSpTq being the elements thereof.
In Equation (1), the constraints limiting the feasible solutions x are formed by two inequality expressions. The inequality expression on the left means that a sum of values of the variable xSpTq obtained between an arbitrary model label Tq and each candidate point Sp belonging to the set P is not more than 1. This means that each model label is mapped with only one of the candidate points or none of the candidate points. The inequality expression on the right means that a sum of values of the variable xSpTq obtained between an arbitrary candidate point Sp and each model label Tq belonging to the set Q is not more than 1. This means that each candidate point is mapped with only one of the model labels or none of the model labels.
However, with the above-described conventional method, where the set of candidate points to be mapped with the model labels is selected from the feasible solutions x belonging to the set C, the selection of the candidate points to be mapped with the model labels as the optimal solution of the evaluation function may be inappropriate, and this is problematic.
For example, as shown in FIG. 11A, when a plurality of candidate points S11 to S19 have been extracted from image data, the candidate points S11, S15, S17 and S19 may be selected as the corresponding points forming a graph structure that matches or is most similar to a shape model Mref1 formed by model labels T11 to T14, and a graph structure Ms1 may be formed by connecting the corresponding points. However, in the graph structure Ms1, the candidate point selected to be mapped with the model label T12, which is located at the branch point of the structure, is inappropriate, resulting in partially overlapped paths connecting the corresponding points. In this case, it is desired to form a graph structure Ms1′, as shown in FIG. 11B, as an appropriate mapping.
Further, as shown in FIG. 12A, for example, when a plurality of candidate points S21 to S27 have been extracted from image data, the candidate points S21, S26 and S27 may be selected as the corresponding points forming a graph structure that matches or is most similar to a shape model Mref2 formed by model labels T21 to T23, and a graph structure Ms2 may be formed by connecting the corresponding points. However, in the graph structure Ms2, the candidate point selected to be mapped with the model label T21, which is located at a branch point of the structure, is inappropriate, resulting in overlapped paths connecting the corresponding points. In this case, it is desired to form a graph structure Ms2′, as shown in FIG. 12B, as an appropriate mapping.